package analysis.lexicalAnalysis;

import domain.StatusInfo;

import java.util.*;

/**
 * DFA的最小化
 */
public class DfaToMini {

    // 状态转化变量
    private String[] chList;

    // NFA确定化后的状态转换表
    private  Map<String, Map<String, String>> statusMap;

    // DFA最小化后的状态转换表
    private Map<String, Map<String, String>> statusSimplifyMap;

    // 每个key对应的Set分组
    Map<String, Set<String>> statusSetMap;

    // 开始状态
    private List<String> startStatus;

    //结束状态
    private List<String> endStatus;

    // 开始状态
    private List<String> newStartStatus;

    //结束状态
    private List<String> newEndStatus;

    public DfaToMini() {
    }

    public DfaToMini(String[] chList, StatusInfo statusInfo) {
        this.chList = chList;
        this.statusMap = statusInfo.getStatusChangeMap();
        this.endStatus = statusInfo.getEndStatus();
        this.startStatus = statusInfo.getStartStatus();
    }

    /**
     * 第一步：获取分割后的等价状态集
     * 第二步：构建旧状态与新的等价状态集的映射
     * 第三步：重构状态转换表
     * @return 返回最小化后的DFA
     */
    public StatusInfo dfaToMini(){
        Set<Set<String>> equivalenceSet = getEquivalenceList();
        System.out.println("+-----------------------------------+");
        System.out.println("|DfaToMini:dfaToMini(): equivalenceSet" + equivalenceSet);
        System.out.println("|DfaToMini:dfaToMini(): statusSetMap" + statusSetMap);
        System.out.println("+-----------------------------------+");

        // 构建等价集与新的状态的映射关系
        Map<Set<String>, String> statusSetToStatus = new HashMap<>();
        int statusCode = 0;
        newStartStatus = new ArrayList<>();
        newEndStatus = new ArrayList<>();
        for(Set<String> statusSet : equivalenceSet){
            statusSetToStatus.put(statusSet, String.valueOf(statusCode++));
            // 获取新的开始状态
            for(String statusSetString : statusSet){
                if(startStatus.contains(statusSetString)){
                    newStartStatus.add(statusSetToStatus.get(statusSet));
                    break;
                }
            }
            // 获取新的结束状态
            for(String statusSetString : statusSet){
                if(endStatus.contains(statusSetString)){
                    newEndStatus.add(statusSetToStatus.get(statusSet));
                    break;
                }
            }
        }
        System.out.println("|DfaToMini:dfaToMini(): statusSetToStatus" + statusSetToStatus);

        statusSimplifyMap = new HashMap<>();
        Set<String> oldKeySet = statusMap.keySet();
        for(String oldKey : oldKeySet){
            String newKey = null;
            String newValue;
            Map<String, String> changeStatus = new HashMap<>();
            for(String change : chList){
                if("ε".equals(change)){ // 如果是ε直接跳过，因为已经NFA确定化了
                    continue;
                }
                String oldValue = statusMap.get(oldKey).get(change);
                newKey = statusSetToStatus.get(statusSetMap.get(oldKey));
                newValue = statusSetToStatus.get(statusSetMap.get(oldValue));
                if(newValue == null){
                    newValue = "^";
                }
                changeStatus.put(change, newValue);
            }
            statusSimplifyMap.put(newKey, changeStatus);
        }
        return new StatusInfo(statusSimplifyMap, newStartStatus, newEndStatus);
    }

    /**
     * 获取等价的状态分组
     * @return 返回分组好后的结果
     */
    private Set<Set<String>> getEquivalenceList(){
        Set<Set<String>> equivalenceList = new HashSet<>();
        Set<String> allStatusKey = statusMap.keySet();  // 所有的状态
        // 初始化状态分组，一个是终态，一个是非终态
        Set<String> isEndStatusSet = new HashSet<>(endStatus);
        Set<String> notEndStatusSet = new HashSet<>();
        for(String status : allStatusKey){
            if( !isEndStatusSet.contains(status)){
                notEndStatusSet.add(status);
            }
        }
        equivalenceList.add(notEndStatusSet);
        equivalenceList.add(isEndStatusSet);
        System.out.println("|DfaToMini:getEquivalenceList():equivalenceList: " + equivalenceList);

        // 每个key对应的Set分组
        statusSetMap = new HashMap<>();
        for(String status : notEndStatusSet){
            statusSetMap.put(status, notEndStatusSet);
        }
        for(String status : isEndStatusSet){
            statusSetMap.put(status,isEndStatusSet);
        }

        // 开始进行分组分割
        Iterator<Set<String>> groupIterator = equivalenceList.iterator();
        int num = 0;
        while (groupIterator.hasNext()) {
            int beforeGroupSize = equivalenceList.size();
            System.out.println("|分组列表迭代:已经迭代了 " + num +  " 次..................");
            Set<String> group = groupIterator.next();
            if (group.size() < 2) { //如果当前分组内元素个数少于两个，直接进行下一组判断
                num++;
                // 迭代次数等于当前分组列表中的组数
                if(equivalenceList.size() == num){
                    break;
                }
                continue;
            }
            for(String change : chList){
                System.out.println("|DfaToMini:getEquivalenceList(): change:" + change);
                Map<String, Set<String>> changedStatus = new HashMap<>();   // 转换后的value值对应key的等价映射分组
                if("ε".equals(change)){ // 如果是ε直接跳过，因为已经NFA确定化了
                    continue;
                }
                Set<String> valueGroup = null;  // 等价Set
                for(String key : group){    // 对当前分组中的每个key求当前change的转换后的值
                    String value = statusMap.get(key).get(change);
                    System.out.println("|DfaToMini:getEquivalenceList(): key:" + key + " change:" + change +  " value:" + value);
                    if("^".equals(value)){  // 不可达时
                        if(changedStatus.containsKey(value)){
                            valueGroup = changedStatus.get(value);
                        }else{
                            valueGroup = new HashSet<>();
                        }
                        valueGroup.add(key);
                        changedStatus.put(value, valueGroup);
                    }else{      // 如果当前的value值是可达状态
                        Set<String> equivalenceStatusSet = statusSetMap.get(value); // 当前状态的等价集
                        boolean existEquivalenceStatus = false;
                        // 查找等价状态分组
                        for(String equivalenceStatus : equivalenceStatusSet){
                            if(changedStatus.containsKey(equivalenceStatus)){
                                valueGroup = changedStatus.get(equivalenceStatus);
                                value = equivalenceStatus;  // 更新value的值为该状态等价集合中已添加到该状态映射map中的key
                                existEquivalenceStatus = true;
                                break;
                            }
                        }
                        // 如果找不到当前的等价状态分组，就创建新的
                        if( !existEquivalenceStatus ){
                            valueGroup = new HashSet<>();
                        }
                    }
                    valueGroup.add(key);
                    changedStatus.put(value, valueGroup);
                    System.out.println("|DfaToMini:getEquivalenceList(): statusSetMap:" + statusSetMap);
                    System.out.println("|DfaToMini:getEquivalenceList(): changedStatus:" + changedStatus);
                }
                // 如果当前的change值中当前分组已经被分割，则在更新分组集后，重新开始下一轮分组
                if(changedStatus.size() > 1){
                    // 将该分组从分组列表中先移除
                    equivalenceList.remove(group);
                    // 一个change值判断完成之后，将新的分组加入分组列表中
                    System.out.println("|DfaToMini:getEquivalenceList(): update:before equivalenceList: " + equivalenceList);
                    Set<String> changedStatusKeys = changedStatus.keySet();
                    for(String changedStatusKey : changedStatusKeys){
                        Set<String> statusGroup = changedStatus.get(changedStatusKey);
                        equivalenceList.add(statusGroup);
                        // 更新状态映射分组表
                        for(String status : statusGroup){
                            statusSetMap.put(status, statusGroup);
                        }
                    }
                    System.out.println("|DfaToMini:getEquivalenceList(): update:after equivalenceList: " + equivalenceList);
                    break;
                }
            }
            // 当前group中前后大小没有发生变化
            if(equivalenceList.size() == beforeGroupSize){
                num++;
                // 迭代次数等于当前分组中组数
                if(equivalenceList.size() == num){
                    System.out.println("|DfaToMini:getEquivalenceList(): here.....equivalenceList.size() == num.......");
                    break;
                }
            }else{  // 当前group中进行判断前后大小发生了变化，需要重新获取迭代器
                // 重新获取迭代器
                groupIterator = equivalenceList.iterator();
                // 迭代计数器重置
                num = 0;
                System.out.println("|DfaToMini:getEquivalenceList(): here:重新获取迭代器.......");
            }
        }
        return equivalenceList;
    }
}
